class Solution {
        int lenh,lenn;
    public int strStr(String haystack, String needle) {
        //kmp算法
        //转换成char提高速度；
        char[] h = haystack.toCharArray();
        char[] n = needle.toCharArray();
        lenh = haystack.length();
        lenn = needle.length();
        if(lenn == 0) return 0;
        int re = kmp(h,n);
        return re;
    }
    //《char 不可以用大写》
    public int kmp(char[] text,char[] pattern){
        int[] match= buildmatch(pattern);
        //i代表遍历text的指针，j代表遍历pattern的指针
        int t = 0, p = 0;
        //直到有指针指到头了结束,如果t到头，没找到；如果p到头，找到
        while( t < lenh && p < lenn){
            //匹配成功的话，同时移动
            if(text[t] == pattern [p]){
                p++;
                t++;
                //匹配不成功的话，
            }else{
                //当p指向第一个元素，t走一个
                if(p == 0){
                    t++;
                }else{
                    //当P有指向的元素，指向前一个数的match，也就是之前数的最大匹配位置
                    p = match[p-1] +1;
                }
            }
        }
        //p走到头，返回t-p 否则返回-1
        return p == lenn ? (t-p) : -1;
    }
    public int[] buildmatch(char[] pattern){
        int[] match = new int[lenn];
        //定义第一个为-1；
        match[0] = -1;
        int pre ;
        for (int i= 1 ; i < lenn ; i++){
            //指针定位到这个元素的前一个元素匹配到的位置
            pre = match[i-1];
            //当前的这个元素不和之前能匹配的最大串的后一个元素匹配的时候
            //最大匹配的元素向前移动，直到移动到头为止
            while (pre >= 0 && pattern[pre+1]!=pattern[i]){
                //a  a  b   a   a  a 
                //0  1  2   3   4  5
        //match//-1  0  -1  0   1  1
                pre = match[pre];
            }
            //当前这个元素和之前能匹配的最大串的后一个元素匹配的时候
            //此时当匹配的就为最大的位置了
            if( pattern[pre+1] == pattern[i]){
                match[i] = pre + 1;
            }else{
                match[i] = -1;
            }
        }
        return match;
    }
}